package T11_20;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T14 {
    public int[][] merge(int[][] intervals) {
        /*
        * 思路：1 先将各个区间按照其起点从小到大排序，遍历区间
        * 2 合并的条件是下一个区间的起点小于等于上一个区间的终点（相交）
        * 3 再比较两个区间的终点，将更大的作为新区间右端点，新区间的左端点不需要更新
        */
        Arrays.sort(intervals,(p,q)->p[0]-q[0]);    //排序
        List<int[]> res=new ArrayList<>();
        for (int[] interval : intervals) {
            int m=res.size();
            if (m>0&&interval[0]<res.get(m-1)[1]){
                res.get(m-1)[1]=Math.max(res.get(m-1)[1],interval[1]);
            }else res.add(interval);
        }
        return res.toArray(new int[res.size()][]);

    }
}
